package binarySortTree;

/**
 * @program: data_structures_algorithms
 * @description: 二叉排序树
 * @author: lld
 * @create: 2020-11-07 16:18
 **/
public class BinarySortTree {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9};
        int[] array = {7, 1, -1, 10, 2,32,-21,6};
        CreateBinarySortTree binarySortTree = new CreateBinarySortTree();
        for (int i = 0; i <arr.length ; i++) {
//            binarySortTree.add(new Node(arr[i]));
            binarySortTree.add(new Node(array[i]));
        }
        binarySortTree.getRoot().inOrder();//中序输出为有序

        deleteNode(binarySortTree.getRoot(), 1);//删除
        System.out.println("删除后：");
        binarySortTree.getRoot().inOrder();//中序输出为有序

    }
    /**
    * @Description: 删除节点
    * @Param: [root, key]
    * @return: binarySortTree.Node
    **/
    public static Node deleteNode(Node root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.value) {
            // 待删除节点在左子树中
            root.left = deleteNode(root.left, key);
            return root;
        } else if (key > root.value) {
            // 待删除节点在右子树中
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            // key == root.value，root 为待删除节点
            if (root.left == null) {
                // 返回右子树作为新的根
                return root.right;
            } else if (root.right == null) {
                // 返回左子树作为新的根
                return root.left;
            } else {
                // 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
                Node successor = min(root.right);
                successor.right = deleteMin(root.right);
                successor.left = root.left;
                return successor;
            }
        }
    }

    private static Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    private static Node deleteMin(Node node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }

}
//创建二叉排序树
class CreateBinarySortTree{
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //添加节点方法
    public void add(Node node){
        if(root==null){
            root=node;
        }else {
            root.addNode(node);
        }
    }
}
class Node{
    int value;
    Node left;
    Node right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
    * @Description: 添加二叉排序节点
    * @Param: [node]
    * @return: void
    **/
    public void addNode(Node node){
        if(node==null){
            return;
        }
        if(node.value<this.value){//比根节点小
            if(this.left==null){//如果当前节点没有左子树
                this.left=node;
            }else {//向左子树递归判断
                this.left.addNode(node);
            }
        }else {//比根节点大或相等
            if(this.right==null){//如果当前节点没有右子树
                this.right=node;
            }else {//向右子树递归判断
                this.right.addNode(node);
            }
        }
    }
    /**
    * @Description: 中序遍历
    * @Param: []
    * @return: void
    **/
    public void inOrder(){
        if(this.left!=null){
            this.left.inOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.inOrder();
        }
    }
}
